package main.java.sort;

import java.util.Arrays;

/**
 * @Author: 郑国荣
 * @Date: 2023-09-10-22:22
 * @Description:
 */
public class QuickSort {

    //快速排序
    //1.选取一个基准值，一般选取第一个元素
    //2.将数组分为两部分，左边的元素都小于基准值，右边的元素都大于基准值
    //3.递归的对左右两部分进行排序
    public void quickSort(int[] arr,int left,int right){
        if (left>=right) return;//递归终止条件
        int pivot = partition(arr, left, right);//获取基准值的位置
        quickSort(arr,left,pivot-1);//对左边的元素进行排序
        quickSort(arr,pivot+1,right);//对右边的元素进行排序
    }


    public int partition(int[] arr,int left,int right){//获取基准值的位置
//        System.out.println("left:"+left+" right:"+right);
//        System.out.println(Arrays.toString(arr));
        int pivot = arr[left];
//        System.out.println("基准值："+pivot);
        int i=left,j=right;
        while (i<j){
            while (i<j && arr[j]>=pivot) j--; //从右边开始找到第一个小于基准值的元素
            while (i<j && arr[i]<=pivot) i++; //从左边开始找到第一个大于基准值的元素
            if (i<j){
                System.out.println("交换："+arr[i]+" "+arr[j]);
                int temp = arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
        arr[left]=arr[i];//arr[i]一定是小于基准值的，因为i是从左边开始的
        arr[i]=pivot; //将基准值放到正确的位置
//        System.out.println("j:"+j+" "+"i:"+i);
        return i;
    }

    public static void main(String[] args) {
        int[] arr = {3,4,2,5,1,6,9,7,8};
        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(arr,0,arr.length-1);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }
}
